package main

import (
	"fmt"
)

func main() {
	nums := []int{2, 2, 3, 3, 3, 4}
	fmt.Println(deleteAndEarn(nums))
}

//给你一个整数数组 nums ，你可以对它进行一些操作。
//
//每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
//
//开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
//链接：https://leetcode-cn.com/problems/delete-and-earn
//题解链接：https://leetcode-cn.com/problems/delete-and-earn/solution/gong-shui-san-xie-zhuan-huan-wei-xu-lie-6c9t0/

//动态规划还是不会啊 ，参考宫水三页的解析
//因为nums[i] 小于 10的4次方,所以可以用x[i]=count ,表示数字i出现了几次
//根据题意，当我们选择 nums[i] 的时候，比 nums[i] 大/小 一个单位的数都不能被选择。 如果我们将数组排好序，从前往后处理，其实只需要考虑“当前数”与“前一个数”的「大小 & 选择」关系即可，这样处理完，显然每个数的「前一位/后一位」都会被考虑到
//dp[i][0]表示不选择数字i的最大代价，因为i不选择，所以i-1可选择也可不选择，即dp[i][0]=max(dp[i-1][0],dp[i-1][1])
//dp[i][1]表示选择数字i的最大代价，因为i已经选择了，所以i-1只能不选,即dp[i][1]=dp[i-1][0]+x[i]*i
func deleteAndEarn(nums []int) int {
	x := make([]int, 10001)
	maxNum := 0
	for _, num := range nums {
		x[num]++
		maxNum = max(maxNum, num)
	}
	dp := make([][2]int, maxNum+1)

	for i := 1; i <= maxNum; i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1])
		dp[i][1] = dp[i-1][0] + x[i]*i
	}
	return max(dp[maxNum][0], dp[maxNum][1])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
